package william.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhangShenao
 * @date 2024/3/5
 * @description <a href="https://leetcode.cn/problems/word-pattern/">...</a>
 */
public class Leetcode290_单词规律 {
    /**
     * 借助Map实现
     * 首先将字符串按照空格进行split分组
     * 然后维护一个pattern->字符串和字符串->pattern的双向映射
     * 针对每一个pattern和字符串,判断对应的映射是否匹配
     * <p>
     * 时间复杂度O(N) 两个字符串各遍历一遍
     * 空间复杂度O(N) 需要额外申请两个Map维护pattern映射关系 N=pattern.length
     */
    public boolean wordPattern(String pattern, String s) {
        //边界条件校验
        if (pattern == null || pattern.isEmpty() || s == null || s.isEmpty()) {
            return false;
        }

        //将字符串按照空格进行split分组
        String[] strs = s.split(" ");
        if (pattern.length() != strs.length) {
            return false;
        }

        //维护一个pattern->字符串和字符串->pattern的双向映射关系
        int N = pattern.length();
        Map<Character, String> patternMap = new HashMap<>(N);
        Map<String, Character> strMap = new HashMap<>(N);

        //针对每一个pattern,判断对应的映射是否匹配
        for (int i = 0; i < pattern.length(); i++) {
            char p = pattern.charAt(i);
            String str = strs[i];
            if (!patternMap.containsKey(p) && !strMap.containsKey(str)) {    //构建双向映射
                patternMap.put(p, str);
                strMap.put(str, p);
                continue;
            }

            //判断pattern映射是否匹配
            if (patternMap.containsKey(p) && !patternMap.get(p).equals(str)) {
                return false;
            }
            if (strMap.containsKey(str) && !strMap.get(str).equals(p)) {
                return false;
            }
        }

        //pattern匹配
        return true;

    }
}
